//题目链接：https://www.luogu.com.cn/problem/P3371#submit
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e5 + 10 , M = 5e6 + 10;

int h[N] , e[M] , ne[M] , w[M] , idx;
int dis[N];
bool st[N];
int n , m , s;
void add(int a , int b , int c)
{
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx++;
}

void spfa(int s)
{
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    st[s] = true;
    while(!q.empty())
    {
        auto t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t] ; i != -1 ; i = ne[i])
        {
            int j = e[i];
            if(dis[j] > dis[t] + w[i])
            {
                dis[j] = dis[t] + w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    memset(h,-1,sizeof h);
    for(int i = 0 ; i < m ; ++i)
    {
        int a , b , c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    spfa(s);
    for(int i = 1 ; i <= n ; ++i)
    {
        if(dis[i] == 0x3f3f3f3f) printf("%d ",0x7fffffff);
        else printf("%d ",dis[i]);
    }
    return 0;
}